package q235

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	find:=root

	//确保 p为小，q为大
	if p.Val>q.Val{
		p,q=q,p
	}

	if p.Val<find.Val && q.Val>find.Val{
		return find
	}

	if q.Val<find.Val{
		//左边
		return lowestCommonAncestor(find.Left,p,q)
	}else if p.Val>find.Val{
		return lowestCommonAncestor(find.Right,p,q)
	}

	return root
}
